This invention relates generally to electronic data processing, and, more particularly, relates to managing the flow of streaming data through multiple processing modules in a computer system.
Continued advances in computer technology have lead to not only increased performance, but also increased performance expectations by the users of such computer equipment. The industry has responded with increased speed for CD ROM drives, communication modems, and faster video and audio cards. These increased user expectations extend not only to hardware capability, but also to the processing capability of data.
For example, in areas such as multimedia and audio compression, a technique known as streaming was developed for transferring data so that it can be processed as a steady and continuous stream. Digital samples representing an audio signal, for example, must be converted to a sound wave in the same sequence the samples were transmitted, and presented at the time spacing they were generated or at a user-specified alternative. Digital data representing video frames must be placed in the proper sequence in a frame and successive frames must be displayed at the correct real-time rate. Streaming technologies are becoming increasingly important with the growth of the Internet because most users do not have fast enough access to download large multimedia files quickly. Streaming data is also used in areas such as video conferencing, digital video discs (DVD), professional audio, telephony, and other areas where audio, video, or audio and video is digitally processed. With streaming, the data can start to be displayed before the entire file has been transmitted.
Streaming data does not need to maintain correct sequence or timing throughout an entire communication chain among the various transmitters, processors, memories, and receivers. For example, audio and video clips are frequently stored as static data in recording media, computer memories, and network buffers. Packet-switched systems might carry parts of the same streaming data over different paths and even in different time sequences. Processors such as digital filters can assemble parts of the data stream, modify them as a static unit, and then release them to other units in the system. However, the stream must be heard and/or seen in the correct sequence at the proper time.
Streaming data almost always requires some form of processing among various modules in a system. For example, a video clip might require MPEG decoding in a dedicated hardware module, rasterizing the video fields in another hardware module, digital filtering of the audio in a software module, insertion of subtitles by another software module, parsing audio data to skip silent periods by a software module, D/A conversion of the video in a video adapter card, and D/A conversion of the audio in a separate audio card. For streaming to work, the data must be processed as a steady stream and then rendered to audio and/or video. If the data isn""t processed quickly enough, however, the presentation of the data will not be smooth.
The concept of a graph was introduced for specifying the connections among the modules that a data stream must pass through for processing in an efficient manner in an effort to increase the data processing speed. Protocols such as WDM-CSA (Windows Driver Model Connection and Streaming Architecture) were developed to specify the flow of data frames through a graph and to specify the control protocol that adjacent modules in the graph use to communicate with each other to request and accept the frames. During connection of modules in a graph, these protocols define a predefined fixed sequence of data flow and control connection negotiations in a graph. A typical negotiation sequence is to negotiate the following in order: the interface, the medium, the data format, the allocators, and the master clock. These architectures have been used to improve the actual data flow only to the extent of reducing inter-buffer data transfers between adjacent modules in the graph.
The simplest and fastest method of controlling the data in a graph is a dedicated protocol for transporting data in frames using a hard-wired, unchanging configuration of modules. Current solutions typically use fixed, hard coded parameters without having a clear concept of the whole graph. For example, some mixer modules are hard coded to have a different size frame buffer depending on the hardware configuration of the system. Additionally, some capture modules will select the number of buffers based on the hardware configuration. At the other extreme, a one-size-fits-all protocol capable of handling a broad spectrum of data types and formats and a wide range of modules has been used. While this protocol is very flexible, and works with a variety of data types, including streaming data, the flexibility almost always sacrifices speed leading often to redundancy and lower efficiency in many graphs.
These architectures and solutions have significant limitations and are not practical for environments such as a multimedia system or personal computer capable of receiving many different kinds of streaming data in multiple formats, and where many manufacturers provide individual modules. One limitation in these systems is that a graph can only have a single clock. For a graph to have a single clock, every other clock in the graph must be able to slave to the single clock. For example, in a relatively simple audio-video graph, the audio-video capture module has its own clock and the audio renderer module has its own clock. For this graph to work, either the capture module or renderer module has to have the capability to rate match its clock to the other module""s clock. If no module in the system has the capability to rate match, then the graph would not work in these systems. These architectures and solutions also do not have the capability to define and solve complex graph timing issues in a graph-wide context and generally do not consider the stream latencies in a graph.
Commonly assigned patent application Ser. No. 09/310,610 xe2x80x9cImproving the Flow of Streaming Data through Multiple Processing Units,xe2x80x9d filed May 12, 1999, provides a partial solution to these limitations by introducing the concept of data pipes for enhancing the data flow of streaming-data frames through a graph of interconnected modules in streaming-data environments. The data pipes avoid redundant storage and copying of data as a number of modules process the data frames, and streamline allocation of the frames in which the data is packaged. Another commonly assigned patent application, Ser. No. 09/310,597, xe2x80x9cImproving the Control of Streaming Data through Multiple. Processors,xe2x80x9d filed May 11, 1999, presents a mechanism for controlling the flow of frames through multiple modules by improving the control from a graph-wide perspective, rather than optimizing each individual module separately. Any control component in the graph that is unnecessary to the overall operation of the graph is removed and the remaining components are then connected directly to each other. Commonly assigned application Ser. No. 09/310,596 xe2x80x9cEfficient Splitting and Mixing of Streaming-Data Frames for Processing Through Multiple Processor Modulesxe2x80x9d, filed May 11, 1999, presents a mechanism for splitting a single frame of streaming data into multiple frames and for combining, merging, or mixing multiple streaming data frames into a single frame. These applications, hereby incorporated by reference, provide partial solutions for increasing efficiencies in processing streaming data to overcome some of the aforementioned limitations.
Accordingly, there therefore exists a continued need for further efficiencies in processing streaming and related types of data in a graph by providing a control mechanism that increases the overall speed of data flowing through the graph, that reduces the systems resources usage, that synchronizes multiple clocks present in a graph, that adaptively controls graphs to achieve low latency graphs, and that achieves the efficiency of a dedicated protocol while allowing enough flexibility of different data types, different modules, and different configurations in the environment of streaming data through multiple processing modules.
In view of the above described problems existing in the art, the present invention provides a system that provides timing and synchronization of streaming data flowing through a graph having multiple modules and having multiple clocks. The system provides a mechanism for splitting the graph into time domains rather than converting all data streams that need to be synchronized into a single master clock that provides the rate of data to the entire graph. A time domain is a set of connections (or pins) in the graph that correspond to the data streams, whose data samples"" time stamps correspond to a common clock. This common clock is called a time domain clock. The system provides an explicit understanding of the relationship between the rates of the clocks in different time domains and constructs a graph that has modules that can span the boundaries between time domains.
Another aspect of the invention is using the explicit understanding of the signal time at different positions in the data streams to control data propagation so that a graph""s latency is at a minimum without a module in the graph running out of data. A further aspect detects when there is a potential for the graph to underrun and dynamically takes corrective action to prevent the graph from running out of data.
In another aspect of the invention, the system analyzes the graph requirements and individual module properties. Using the interdependent concepts of data flow, control, and timing and synchronization an acceptable solution for the pipe configuration, the time domain configuration, and the flow control configuration is derived where solutions exist. Once a solution is determined, the system translates the solution into requirements for the individual modules and streaming framework modules of the graph.
Additional features and advantages of the invention will be made apparent from the following detailed description of illustrative embodiments that proceeds with reference to the accompanying figures.